/*
 * [53] 数字在排序数组中出现的次数
 * 统计一个数字在排序数组中出现的次数
 * 由于是有序的，可以用二分查找，找到该数第一次出现的位置和最后一次出现的位置，计算次数即可
 *
 *
 *
 *
 *
 *
 *
 *
 * g++ test_cpp.cpp -ggdb -std=c++11
 */

// @lc code=start

// 回顾普通的二分查找
/**
int binarysearch(vector<int>& a, int k) {
  int left = 0;
  int right = a.size() - 1;
  int mid;
  while (left <= right) {
    mid = (left + right) / 2;
    // k较a[mid]大时，在右半区间查找
    if (a[mid] < k) left = mid + 1;
    // k较a[mid]小时，在右半区间查找
    else if (a[mid] > k)
      right = mid - 1;
    // 若相等则返回mid
    else
      return mid;
  }
  // 找不到时返回-1
  return -1；
}
**/

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
 public:
  int GetNumberOfK(vector<int>& data, int k) {
    if (data.empty()) return 0;
    int first = getFirst(data, k);
    int last = getLast(data, k);
    if (first != -1 && last != -1)
      return last - first + 1;
    else
      return 0;
  }

 private:
  int getFirst(vector<int>& a, int k) {
    int left = 0;
    int right = a.size() - 1;
    int mid;
    while (left <= right) {
      mid = right + (left - right) / 2;
      // 二分搜索
      if (a[mid] < k)
        left = mid + 1;
      else if (a[mid] > k)
        right = mid - 1;
      // 当前数等于k,前一个数也等于k时，继续在左半区间查找
      else if (mid - 1 >= 0 && a[mid - 1] == k)
        right = mid - 1;
      // 当前数等于k,前一个数不等于k或者为开头时，返回mi
      else
        return mid;
    }
  }

  int getLast(vector<int>& a, int target) {
    int left = 0;
    int right = a.size() - 1;
    int mid;
    // 二分搜索开始
    while (left <= right) {
      mid = left + right >> 1;
      if (a[mid] < target)
        left = mid + 1;
      else if (target < a[mid])
        right = mid - 1;
      else if (mid + 1 < a.size() && a[mid + 1] == target)
        left = mid + 1;
      else
        return mid;
    }
    return -1;
  }
};

int main() {
  class Solution solute;
  vector<int> arra1 = {1, 2, 2, 3};
  vector<int> arra2 = {1, 2, 2, 3};
  int result1 = solute.GetNumberOfK(arra1, 1);
  int result2 = solute.GetNumberOfK(arra2, 2);

  cout << "sum1: " << result1 << endl;
  cout << "sum2: " << result2 << endl;

  return 0;
}

// @lc code=end
